{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Painting a Grid With Three Different Colors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: colorTheGrid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #用三种不同颜色为网格涂色"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数 <code>m</code> 和 <code>n</code> 。构造一个 <code>m x n</code> 的网格，其中每个单元格最开始是白色。请你用 <strong>红、绿、蓝</strong> 三种颜色为每个单元格涂色。所有单元格都需要被涂色。</p>\n",
    "\n",
    "<p>涂色方案需要满足：<strong>不存在相邻两个单元格颜色相同的情况</strong> 。返回网格涂色的方法数。因为答案可能非常大， 返回 <strong>对 </strong><code>10<sup>9</sup> + 7</code><strong> 取余</strong> 的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/22/colorthegrid.png\" style=\"width: 200px; height: 50px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 1, n = 1\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>如上图所示，存在三种可能的涂色方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/22/copy-of-colorthegrid.png\" style=\"width: 321px; height: 121px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 1, n = 2\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>如上图所示，存在六种可能的涂色方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 5, n = 5\n",
    "<strong>输出：</strong>580986\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= m <= 5</code></li>\n",
    "\t<li><code>1 <= n <= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [painting-a-grid-with-three-different-colors](https://leetcode.cn/problems/painting-a-grid-with-three-different-colors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [painting-a-grid-with-three-different-colors](https://leetcode.cn/problems/painting-a-grid-with-three-different-colors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1', '1\\n2', '5\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        d = {}\n",
    "        M = 10 ** 9 + 7\n",
    "        for state in range(4 ** m):\n",
    "            t = [0] * m\n",
    "            tmp = state\n",
    "            for i in range(m):\n",
    "                t[i] = k = state & 3\n",
    "                if k == 3 or (i > 0 and k == t[i - 1]):\n",
    "                    break\n",
    "                state >>= 2\n",
    "            else:\n",
    "                d[tmp] = t\n",
    "        # print(d)\n",
    "        ok = defaultdict(list)\n",
    "        f = [{}, {}]\n",
    "        for state, t in d.items():\n",
    "            f[0][state] = 1\n",
    "            for state2, t2 in d.items():\n",
    "                if all(t[i] != t2[i] for i in range(m)):\n",
    "                    ok[state].append(state2)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            now = i & 1\n",
    "            pre = now ^ 1\n",
    "            for state in d.keys():\n",
    "                f[now][state] = 0\n",
    "            # print(f, pre)    \n",
    "            for state, v in f[pre].items():\n",
    "                for state2 in ok[state]:\n",
    "                    f[now][state2] = (f[now][state2] + f[pre][state]) % M\n",
    "        return sum(f[(n - 1) & 1].values()) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class mySystem:\n",
    "    def __init__(self, n, system=3) -> None:\n",
    "        self.v = [0] * n\n",
    "        self.Len = n\n",
    "        self.system = system\n",
    "\n",
    "    def __iter__(self):\n",
    "        q = [(0, i) for i in range(self.system)]\n",
    "      \n",
    "        while q:\n",
    "            i, vv = q.pop()\n",
    "            if i == self.Len:\n",
    "                yield tuple(self.v)\n",
    "            else:\n",
    "                self.v[i] = vv\n",
    "                for j in range(self.system):\n",
    "                    q.append((i+1, j))\n",
    "             \n",
    "           \n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案\n",
    "        # 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）\n",
    "        valid = set()\n",
    "        \n",
    "        # 在 [0, 3^m) 范围内枚举满足要求的 mask\n",
    "        for color in mySystem(m):\n",
    "    \n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            valid.add(color)\n",
    "        \n",
    "        # 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同\n",
    "        adjacent = defaultdict(list)\n",
    "        for color1 in valid:\n",
    "            for color2 in valid:\n",
    "                if not any(x == y for x, y in zip(color1, color2)):\n",
    "                    adjacent[color1].append(color2)\n",
    "        \n",
    "        f = {mask:int(mask in valid) for mask in mySystem(m)}\n",
    "        for i in range(1, n):\n",
    "            g = defaultdict(int)\n",
    "            for mask2 in valid:\n",
    "                for mask1 in adjacent[mask2]:\n",
    "                    g[mask2] += f[mask1]\n",
    "                    if g[mask2] >= mod:\n",
    "                        g[mask2] -= mod\n",
    "            f = g\n",
    "            \n",
    "        return sum(f.values()) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class mySystem:\n",
    "    def __init__(self, n, system=3) -> None:\n",
    "        self.v = [0] * n\n",
    "        self.Len = n\n",
    "        self.system = system\n",
    "\n",
    "    def __iter__(self):\n",
    "        q = [(0, i) for i in range(self.system)]\n",
    "      \n",
    "        while q:\n",
    "            i, vv = q.pop()\n",
    "            if i == self.Len:\n",
    "                yield tuple(self.v)\n",
    "            else:\n",
    "                self.v[i] = vv\n",
    "                for j in range(self.system):\n",
    "                    q.append((i+1, j))\n",
    "             \n",
    "           \n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案\n",
    "        # 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）\n",
    "        valid = set()\n",
    "        \n",
    "        # 在 [0, 3^m) 范围内枚举满足要求的 mask\n",
    "        for color in mySystem(m):\n",
    "    \n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            valid.add(color)\n",
    "        \n",
    "        # 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同\n",
    "        adjacent = defaultdict(list)\n",
    "        for color1 in valid:\n",
    "            for color2 in valid:\n",
    "                if not any(x == y for x, y in zip(color1, color2)):\n",
    "                    adjacent[color1].append(color2)\n",
    "        \n",
    "        f = {mask:int(mask in valid) for mask in mySystem(m)}\n",
    "        for i in range(1, n):\n",
    "            g = defaultdict(int)\n",
    "            for mask2 in valid:\n",
    "                for mask1 in adjacent[mask2]:\n",
    "                    g[mask2] += f[mask1]\n",
    "                    if g[mask2] >= mod:\n",
    "                        g[mask2] -= mod\n",
    "            f = g\n",
    "            \n",
    "        return sum(f.values()) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        d = {}\n",
    "        M = 10 ** 9 + 7\n",
    "        for state in range(4 ** m):\n",
    "            t = [0] * m\n",
    "            tmp = state\n",
    "            for i in range(m):\n",
    "                t[i] = k = state & 3\n",
    "                if k == 3 or (i > 0 and k == t[i - 1]):\n",
    "                    break\n",
    "                state >>= 2\n",
    "            else:\n",
    "                d[tmp] = t\n",
    "        # print(d)\n",
    "        ok = defaultdict(list)\n",
    "        f = [{}, {}]\n",
    "        for state, t in d.items():\n",
    "            f[0][state] = 1\n",
    "            for state2, t2 in d.items():\n",
    "                if all(t[i] != t2[i] for i in range(m)):\n",
    "                    ok[state].append(state2)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            now = i & 1\n",
    "            pre = now ^ 1\n",
    "            for state in d.keys():\n",
    "                f[now][state] = 0\n",
    "            for state, v in f[pre].items():\n",
    "                for state2 in ok[state]:\n",
    "                    f[now][state2] += f[pre][state]\n",
    "                    if f[now][state2] >= M:\n",
    "                        f[now][state2] -= M\n",
    "        return sum(f[(n - 1) & 1].values()) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        M = 3 ** m\n",
    "        dc = defaultdict(list)\n",
    "        ps = set()\n",
    "        for i in range(M//9, M):\n",
    "            srt, ni, last = 0, i, -1\n",
    "            while i:\n",
    "                if last == i % 3: break\n",
    "                last = i % 3\n",
    "                i //= 3\n",
    "            else: ps.add(ni)\n",
    "        print(ps)\n",
    "        for ni in ps:\n",
    "            lis, srt, i = [0] * m, 0, ni\n",
    "            while i:\n",
    "                lis[srt] = i % 3\n",
    "                i //= 3\n",
    "                srt += 1\n",
    "            for nj in ps:\n",
    "                j = nj\n",
    "                for k in lis:\n",
    "                    if k == j % 3:\n",
    "                        break\n",
    "                    j //= 3\n",
    "                else:\n",
    "                    dc[ni].append(nj)\n",
    "        lis = [1 if i in ps else 0 for i in range(M)]\n",
    "        for _ in range(n-1):\n",
    "            nlis = [0] * M\n",
    "            for j in range(M):\n",
    "                v = lis[j]\n",
    "                for k in dc[j]:\n",
    "                    nlis[k] += v\n",
    "            lis = [i % 1000000007 for i in nlis]\n",
    "        return sum(lis) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        \n",
    "        # 预处理所有的横向合法情况\n",
    "        d = {}\n",
    "        for state in range(3 ** m):\n",
    "            colors = []\n",
    "            t = state\n",
    "            for i in range(m):\n",
    "                colors.append(state % 3)\n",
    "                state //= 3\n",
    "            if all(colors[i] != colors[i + 1] for i in range(m - 1)):\n",
    "                d[t] = colors\n",
    "\n",
    "        # 预处理竖向的合法情况\n",
    "        used = defaultdict(list)\n",
    "        for state, colors in d.items():\n",
    "            for state2, colors2 in d.items():\n",
    "                if all(x != y for x, y in zip(colors, colors2)):\n",
    "                    used[state].append(state2)\n",
    "        \n",
    "        f = [int(state in d) for state in range(3 ** m)]\n",
    "        for i in range(1, n):\n",
    "            g = [0] * (3 ** m)\n",
    "            for state in d.keys():\n",
    "                for state2 in used[state]:\n",
    "                    g[state] += f[state2]\n",
    "                    g[state] %= MOD\n",
    "            f = g\n",
    "        return sum(f) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class mySystem:\n",
    "    def __init__(self, n, system=3) -> None:\n",
    "        self.v = [0] * n\n",
    "        self.Len = n\n",
    "        self.system = system\n",
    "\n",
    "    def __iter__(self):\n",
    "        q = [(0, 0), (0, 1), (0, 2)]\n",
    "      \n",
    "        while q:\n",
    "            i, vv = q.pop()\n",
    "            if i == self.Len:\n",
    "                yield tuple(self.v)\n",
    "            else:\n",
    "                self.v[i] = vv\n",
    "                for j in range(self.system):\n",
    "                    q.append((i+1, j))\n",
    "             \n",
    "           \n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案\n",
    "        # 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）\n",
    "        valid = set()\n",
    "        \n",
    "        # 在 [0, 3^m) 范围内枚举满足要求的 mask\n",
    "        for color in mySystem(m):\n",
    "    \n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            valid.add(color)\n",
    "        \n",
    "        # 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同\n",
    "        adjacent = defaultdict(list)\n",
    "        for color1 in valid:\n",
    "            for color2 in valid:\n",
    "                if not any(x == y for x, y in zip(color1, color2)):\n",
    "                    adjacent[color1].append(color2)\n",
    "        \n",
    "        f = {mask:int(mask in valid) for mask in mySystem(m)}\n",
    "        for i in range(1, n):\n",
    "            g = defaultdict(int)\n",
    "            for mask2 in valid:\n",
    "                for mask1 in adjacent[mask2]:\n",
    "                    g[mask2] += f[mask1]\n",
    "                    if g[mask2] >= mod:\n",
    "                        g[mask2] -= mod\n",
    "            f = g\n",
    "            \n",
    "        return sum(f.values()) % mod\n",
    "    \n",
    "\n",
    "# print(Solution().colorTheGrid(5, 5)) # 80986"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        d = {}\n",
    "        for mask in range(3 ** m):\n",
    "            t = mask\n",
    "            color = []\n",
    "            for i in range(m):\n",
    "                color.append(t % 3)\n",
    "                t //= 3\n",
    "            if all(color[i] != color[i + 1] for i in range(m - 1)):\n",
    "                d[mask] = color\n",
    "        \n",
    "        used = defaultdict(list)\n",
    "        for mask, color in d.items():\n",
    "            for mask2, color2 in d.items():\n",
    "                if all(x != y for x, y in zip(color, color2)):\n",
    "                    used[mask].append(mask2)\n",
    "        \n",
    "        f = [int(mask in d) for mask in range(3 ** m)]\n",
    "        for _ in range(1, n):\n",
    "            g = [0] * (3 ** m)\n",
    "            for mask in d.keys():\n",
    "                for mask2 in used[mask]:\n",
    "                    g[mask] += f[mask2]\n",
    "                    g[mask] %= MOD\n",
    "            f = g\n",
    "        return sum(f) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案\n",
    "        # 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）\n",
    "        valid = dict()\n",
    "        \n",
    "        # 在 [0, 3^m) 范围内枚举满足要求的 mask\n",
    "        for mask in range(3**m):\n",
    "            color = list()\n",
    "            mm = mask\n",
    "            for i in range(m):\n",
    "                color.append(mm % 3)\n",
    "                mm //= 3\n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            valid[mask] = color\n",
    "        \n",
    "        # 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同\n",
    "        adjacent = defaultdict(list)\n",
    "        for mask1, color1 in valid.items():\n",
    "            for mask2, color2 in valid.items():\n",
    "                if not any(x == y for x, y in zip(color1, color2)):\n",
    "                    adjacent[mask1].append(mask2)\n",
    "        \n",
    "        f = [int(mask in valid) for mask in range(3**m)]\n",
    "        for i in range(1, n):\n",
    "            g = [0] * (3**m)\n",
    "            for mask2 in valid.keys():\n",
    "                for mask1 in adjacent[mask2]:\n",
    "                    g[mask2] += f[mask1]\n",
    "                    if g[mask2] >= mod:\n",
    "                        g[mask2] -= mod\n",
    "            f = g\n",
    "            \n",
    "        return sum(f) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        d = {}\n",
    "        for mask in range(3 ** m):\n",
    "            x = []\n",
    "            t = mask\n",
    "            for j in range(m):\n",
    "                x.append(mask % 3)\n",
    "                mask //= 3\n",
    "            if all(x[i] != x[i + 1] for i in range(m - 1)):\n",
    "                d[t] = x\n",
    "        # print(\"d\", d)\n",
    "        use = defaultdict(list)\n",
    "        for k, v in d.items():\n",
    "            for k2, v2 in d.items():\n",
    "                if all(x != y for x, y in zip(v, v2)):\n",
    "                    use[k].append(k2)\n",
    "        f = [int(x in d) for x in range(3 ** m)]\n",
    "        # print(f)\n",
    "        for i in range(1, n):\n",
    "            g = [0] * (3 ** m)\n",
    "            for mask in d:\n",
    "                for mask2 in use[mask]:\n",
    "                    g[mask] += f[mask2]\n",
    "                    g[mask] %= MOD\n",
    "            f = g\n",
    "        # print(f)\n",
    "        return sum(f) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        d = {}\n",
    "        for mask in range(3**m):\n",
    "            color = list()\n",
    "            mm = mask\n",
    "            for i in range(m):\n",
    "                color.append(mm % 3)\n",
    "                mm //= 3\n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            d[mask] = color\n",
    "        adjacent = defaultdict(list)\n",
    "        for mask1, color1 in d.items():\n",
    "            for mask2, color2 in d.items():\n",
    "                if not any(x == y for x, y in zip(color1, color2)):\n",
    "                    adjacent[mask1].append(mask2)\n",
    "        f = [int(mask in d) for mask in range(3**m)]\n",
    "        for i in range(1, n):\n",
    "            g = [0] * (3**m)\n",
    "            for mask2 in d.keys():\n",
    "                for mask1 in adjacent[mask2]:\n",
    "                    g[mask2] += f[mask1]\n",
    "                    g[mask2]%=1000000007\n",
    "            f = g.copy()\n",
    "            \n",
    "        return sum(f) %1000000007\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        M = 3 ** m\n",
    "        dc = defaultdict(list)\n",
    "        ps = set()\n",
    "        for i in range(M//9, M):\n",
    "            srt, ni, last = 0, i, -1\n",
    "            while i:\n",
    "                if last == i % 3: break\n",
    "                last = i % 3\n",
    "                i //= 3\n",
    "            else: ps.add(ni)\n",
    "        for ni in ps:\n",
    "            lis, srt, i = [0] * m, 0, ni\n",
    "            while i:\n",
    "                lis[srt] = i % 3\n",
    "                i //= 3\n",
    "                srt += 1\n",
    "            for nj in ps:\n",
    "                j = nj\n",
    "                for k in lis:\n",
    "                    if k == j % 3:\n",
    "                        break\n",
    "                    j //= 3\n",
    "                else:\n",
    "                    dc[ni].append(nj)\n",
    "        lis = [1 if i in ps else 0 for i in range(M)]\n",
    "        for _ in range(n-1):\n",
    "            nlis = [0] * M\n",
    "            for j in range(M):\n",
    "                v = lis[j]\n",
    "                for k in dc[j]:\n",
    "                    nlis[k] += v\n",
    "            lis = [i % 1000000007 for i in nlis]\n",
    "        return sum(lis) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        def f1(x: int) -> bool:\n",
    "            last = -1\n",
    "            for _ in range(m):\n",
    "                if x % 3 == last:\n",
    "                    return False\n",
    "                last = x % 3\n",
    "                x //= 3\n",
    "            return True\n",
    "\n",
    "        def f2(x: int, y: int) -> bool:\n",
    "            for _ in range(m):\n",
    "                if x % 3 == y % 3:\n",
    "                    return False\n",
    "                x, y = x // 3, y // 3\n",
    "            return True\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        mx = 3**m\n",
    "        valid = {i for i in range(mx) if f1(i)}\n",
    "        d = defaultdict(list)\n",
    "        for x in valid:\n",
    "            for y in valid:\n",
    "                if f2(x, y):\n",
    "                    d[x].append(y)\n",
    "        f = [int(i in valid) for i in range(mx)]\n",
    "        for _ in range(n - 1):\n",
    "            g = [0] * mx\n",
    "            for i in valid:\n",
    "                for j in d[i]:\n",
    "                    g[i] = (g[i] + f[j]) % mod\n",
    "            f = g\n",
    "        return sum(f) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        M = 3 ** m\n",
    "        dc = defaultdict(list)\n",
    "        ps = set()\n",
    "        for i in range(M//9, M):\n",
    "            srt, ni, last = 0, i, -1\n",
    "            while i:\n",
    "                if last == i % 3: break\n",
    "                last = i % 3\n",
    "                i //= 3\n",
    "            else: ps.add(ni)\n",
    "        for ni in ps:\n",
    "            lis, srt, i = [0] * m, 0, ni\n",
    "            while i:\n",
    "                lis[srt] = i % 3\n",
    "                i //= 3\n",
    "                srt += 1\n",
    "            for nj in ps:\n",
    "                j = nj\n",
    "                for k in lis:\n",
    "                    if k == j % 3:\n",
    "                        break\n",
    "                    j //= 3\n",
    "                else:\n",
    "                    dc[ni].append(nj)\n",
    "        lis = [1 if i in ps else 0 for i in range(M)]\n",
    "        for _ in range(n-1):\n",
    "            nlis = [0] * M\n",
    "            for j in range(M):\n",
    "                v = lis[j]\n",
    "                for k in dc[j]:\n",
    "                    nlis[k] = (nlis[k] + v) % 1000000007\n",
    "            lis = nlis\n",
    "        return sum(lis) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案\n",
    "        # 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）\n",
    "        valid = dict()\n",
    "        \n",
    "        # 在 [0, 3^m) 范围内枚举满足要求的 mask\n",
    "        for mask in range(3**m):\n",
    "            color = list()\n",
    "            mm = mask\n",
    "            for i in range(m):\n",
    "                color.append(mm % 3)\n",
    "                mm //= 3\n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            valid[mask] = color\n",
    "        \n",
    "        # 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同\n",
    "        adjacent = defaultdict(list)\n",
    "        for mask1, color1 in valid.items():\n",
    "            for mask2, color2 in valid.items():\n",
    "                if not any(x == y for x, y in zip(color1, color2)):\n",
    "                    adjacent[mask1].append(mask2)\n",
    "        \n",
    "        f = [int(mask in valid) for mask in range(3**m)]\n",
    "        for i in range(1, n):\n",
    "            g = [0] * (3**m)\n",
    "            for mask2 in valid.keys():\n",
    "                for mask1 in adjacent[mask2]:\n",
    "                    g[mask2] += f[mask1]\n",
    "                    if g[mask2] >= mod:\n",
    "                        g[mask2] -= mod\n",
    "            f = g\n",
    "            \n",
    "        return sum(f) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        M = 3 ** m\n",
    "        dc = defaultdict(list)\n",
    "        ps = set()\n",
    "        for i in range(M//9, M):\n",
    "            srt, ni, last = 0, i, -1\n",
    "            while i:\n",
    "                if last == i % 3: break\n",
    "                last = i % 3\n",
    "                i //= 3\n",
    "            else: ps.add(ni)\n",
    "        for ni in ps:\n",
    "            lis, srt, i = [0] * m, 0, ni\n",
    "            while i:\n",
    "                lis[srt] = i % 3\n",
    "                i //= 3\n",
    "                srt += 1\n",
    "            for nj in ps:\n",
    "                j = nj\n",
    "                for k in lis:\n",
    "                    if k == j % 3:\n",
    "                        break\n",
    "                    j //= 3\n",
    "                else:\n",
    "                    dc[ni].append(nj)\n",
    "        lis = [1 if i in ps else 0 for i in range(M)]\n",
    "        for _ in range(n-1):\n",
    "            nlis = [0] * M\n",
    "            for j in range(M):\n",
    "                v = lis[j]\n",
    "                for k in dc[j]:\n",
    "                    nlis[k] = (nlis[k] + v % 1000000007)\n",
    "            lis = nlis\n",
    "        return sum(lis) % 1000000007\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class ternary:\n",
    "    def __init__(self, n) -> None:\n",
    "        self.v = [0] * n\n",
    "        self.Len = n\n",
    "\n",
    "    def __iter__(self):\n",
    "        q = [(0, 0), (0, 1), (0, 2)]\n",
    "      \n",
    "        while q:\n",
    "            i, vv = q.pop()\n",
    "            if i == self.Len:\n",
    "                yield tuple(self.v)\n",
    "            else:\n",
    "                self.v[i] = vv\n",
    "                for j in range(3):\n",
    "                    q.append((i+1, j))\n",
    "             \n",
    "           \n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案\n",
    "        # 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）\n",
    "        valid = set()\n",
    "        \n",
    "        # 在 [0, 3^m) 范围内枚举满足要求的 mask\n",
    "        for color in ternary(m):\n",
    "    \n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            valid.add(color)\n",
    "        \n",
    "        # 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同\n",
    "        adjacent = defaultdict(list)\n",
    "        for color1 in valid:\n",
    "            for color2 in valid:\n",
    "                if not any(x == y for x, y in zip(color1, color2)):\n",
    "                    adjacent[color1].append(color2)\n",
    "        \n",
    "        f = {mask:int(mask in valid) for mask in ternary(m)}\n",
    "        for i in range(1, n):\n",
    "            g = defaultdict(int)\n",
    "            for mask2 in valid:\n",
    "                for mask1 in adjacent[mask2]:\n",
    "                    g[mask2] += f[mask1]\n",
    "                    if g[mask2] >= mod:\n",
    "                        g[mask2] -= mod\n",
    "            f = g\n",
    "            \n",
    "        return sum(f.values()) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "f[i][mask] 表示我们已经对 0,1,⋯ ,i 行进行了涂色，并且第 i 行的涂色方案对应的三进制表示为 mask 的前提下的总方案数。\n",
    "'''\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 哈希映射 valid 存储所有满足要求的对一行进行涂色的方案\n",
    "        # 键表示 mask，值表示 mask 的三进制串（以列表的形式存储）\n",
    "        valid = dict()\n",
    "        \n",
    "        # 在 [0, 3^m) 范围内枚举满足要求的 mask\n",
    "        for mask in range(3**m):\n",
    "            color = list()\n",
    "            mm = mask\n",
    "            for i in range(m):\n",
    "                color.append(mm % 3)\n",
    "                mm //= 3\n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            valid[mask] = color\n",
    "        \n",
    "        # 预处理所有的 (mask1, mask2) 二元组，满足 mask1 和 mask2 作为相邻行时，同一列上两个格子的颜色不同\n",
    "        adjacent = defaultdict(list)\n",
    "        for mask1, color1 in valid.items():\n",
    "            for mask2, color2 in valid.items():\n",
    "                if not any(x == y for x, y in zip(color1, color2)):\n",
    "                    adjacent[mask1].append(mask2)\n",
    "        \n",
    "        f = [int(mask in valid) for mask in range(3**m)]\n",
    "        for i in range(1, n):\n",
    "            g = [0] * (3**m)\n",
    "            for mask2 in valid.keys():\n",
    "                for mask1 in adjacent[mask2]:\n",
    "                    g[mask2] += f[mask1]\n",
    "                    if g[mask2] >= mod:\n",
    "                        g[mask2] -= mod\n",
    "            f = g\n",
    "            \n",
    "        return sum(f) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        m,n=n,m\n",
    "        types = []\n",
    "\n",
    "        def dfs(i, path: List[int]):\n",
    "            if i == n:\n",
    "                types.append(list(path))\n",
    "                return\n",
    "            for j in range(3):\n",
    "                if not path:\n",
    "                    path.append(j)\n",
    "                    dfs(i + 1, path)\n",
    "                    path.pop()\n",
    "                elif path[-1] != j:\n",
    "                    path.append(j)\n",
    "                    dfs(i + 1, path)\n",
    "                    path.pop()\n",
    "        dfs(0,[])\n",
    "        typesCnt=len(types)\n",
    "        canType=[[0]* typesCnt for _ in range(typesCnt)]\n",
    "        for i in range(typesCnt):\n",
    "            for j in range(typesCnt):\n",
    "                if i!=j  and not any (x==y for x,y in zip(types[i],types[j])):\n",
    "                    canType[i][j]=1\n",
    "        dp=[[0]* typesCnt for _ in range(m)]\n",
    "        mod=10**9+7\n",
    "        for j in range(typesCnt):\n",
    "            dp[0][j]=1\n",
    "        for i in range(1,m):\n",
    "            for j in range(typesCnt):\n",
    "                for k in range(typesCnt):\n",
    "                    if canType[j][k]==1:\n",
    "                        dp[i][j]+=dp[i-1][k]\n",
    "                        dp[i][j]%=mod\n",
    "        return sum(dp[m-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        \n",
    "        def is_valid(p1, p2, m):\n",
    "            for i in range(m):\n",
    "                if p1[i] == p2[i]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def generate_patterns(m):\n",
    "            if m == 1:\n",
    "                return [[0], [1], [2]]\n",
    "            \n",
    "            smaller_patterns = generate_patterns(m - 1)\n",
    "            patterns = []\n",
    "            \n",
    "            for sp in smaller_patterns:\n",
    "                for color in range(3):\n",
    "                    if sp[-1] != color:\n",
    "                        patterns.append(sp + [color])\n",
    "                        \n",
    "            return patterns\n",
    "        \n",
    "        all_patterns = generate_patterns(m)\n",
    "        \n",
    "        dp = [[0 for _ in range(len(all_patterns))] for _ in range(n)]\n",
    "        \n",
    "        for i in range(len(all_patterns)):\n",
    "            dp[0][i] = 1\n",
    "\n",
    "        for col in range(1, n):\n",
    "            for p1 in range(len(all_patterns)):\n",
    "                for p2 in range(len(all_patterns)):\n",
    "                    if is_valid(all_patterns[p1], all_patterns[p2], m):\n",
    "                        dp[col][p1] += dp[col-1][p2]\n",
    "                        dp[col][p1] %= MOD\n",
    "        \n",
    "        return sum(dp[-1]) % MOD\n",
    "\n",
    "# Example\n",
    "sol = Solution()\n",
    "print(sol.colorTheGrid(5, 5))  # Should print 580986\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        m,n=n,m\n",
    "        types = []\n",
    "\n",
    "        def dfs(i, path: List[int]):\n",
    "            if i == n:\n",
    "                types.append(list(path))\n",
    "                return\n",
    "            for j in range(3):\n",
    "                if not path:\n",
    "                    path.append(j)\n",
    "                    dfs(i + 1, path)\n",
    "                    path.pop()\n",
    "                elif path[-1] != j:\n",
    "                    path.append(j)\n",
    "                    dfs(i + 1, path)\n",
    "                    path.pop()\n",
    "        dfs(0,[])\n",
    "        typesCnt=len(types)\n",
    "        canType=[[0]* typesCnt for _ in range(typesCnt)]\n",
    "        def isCan(a,b):\n",
    "            for k in range(n):\n",
    "                if a[k]==b[k]:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for i in range(typesCnt):\n",
    "            for j in range(typesCnt):\n",
    "                if i!=j  and isCan(types[i],types[j]):\n",
    "                    canType[i][j]=1\n",
    "        dp=[[0]* typesCnt for _ in range(m)]\n",
    "        mod=10**9+7\n",
    "        for j in range(typesCnt):\n",
    "            dp[0][j]=1\n",
    "        for i in range(1,m):\n",
    "            for j in range(typesCnt):\n",
    "                for k in range(typesCnt):\n",
    "                    if canType[j][k]==1:\n",
    "                        dp[i][j]+=dp[i-1][k]\n",
    "                        dp[i][j]%=mod\n",
    "        return sum(dp[m-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        up = pow(3, m)\n",
    "        valid = []\n",
    "        match = defaultdict(list)\n",
    "\n",
    "        for num in range(up):\n",
    "            color = [0] * m\n",
    "            tmp = num\n",
    "            pos = 0\n",
    "            while tmp:\n",
    "                color[pos] = tmp % 3\n",
    "                pos += 1\n",
    "                tmp //= 3\n",
    "            #print(color)\n",
    "            if any(color[i] == color[i + 1] for i in range(m - 1)):\n",
    "                continue\n",
    "            valid.append(num)\n",
    "        \n",
    "        #print(valid)\n",
    "\n",
    "        for x in valid:\n",
    "            for y in valid:\n",
    "                colorx = [0] * m\n",
    "                tmp = x\n",
    "                pos = 0\n",
    "                while tmp:\n",
    "                    colorx[pos] = tmp % 3\n",
    "                    pos += 1\n",
    "                    tmp //= 3\n",
    "                colory = [0] * m\n",
    "                tmp = y\n",
    "                pos = 0\n",
    "                while tmp:\n",
    "                    colory[pos] = tmp % 3\n",
    "                    pos += 1\n",
    "                    tmp //= 3\n",
    "                if all(colorx[i] != colory[i] for i in range(m)):\n",
    "                    match[x].append(y)\n",
    "        #print(match)\n",
    "        f = [[0] * up for _ in range(n)]\n",
    "        for val in valid:\n",
    "            f[0][val] = 1\n",
    "        for i in range(1, n):\n",
    "            for val in valid:\n",
    "                for pre_val in match[val]:\n",
    "                    f[i][val] = (f[i][val] + f[i - 1][pre_val]) % MOD\n",
    "\n",
    "        return sum(f[n - 1]) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "\n",
    "        full_mask =3**m\n",
    "        MODX = 10**9+7 \n",
    "\n",
    "        def row_not_same(prev,mask,i):\n",
    "            if i==m:\n",
    "                return True \n",
    "            x = mask%3\n",
    "            if x==prev:\n",
    "                return False \n",
    "            return row_not_same(x,mask//3,i+1)\n",
    "\n",
    "        def col_not_same(mask_a,mask_b,i):\n",
    "            if i==m:\n",
    "                return True \n",
    "            x,y = mask_a%3, mask_b%3\n",
    "            if x==y:\n",
    "                return False \n",
    "            return col_not_same(mask_a//3, mask_b//3,i+1)\n",
    "\n",
    "        valid_masks = []\n",
    "        for mask in range(full_mask):\n",
    "            if row_not_same(-1,mask,0):\n",
    "                valid_masks.append(mask)\n",
    "\n",
    "        adjacent = collections.defaultdict(list)\n",
    "        for mask1 in valid_masks:\n",
    "            for mask2 in valid_masks:\n",
    "                if col_not_same(mask1, mask2, 0):\n",
    "                    adjacent[mask1].append(mask2)\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "        \n",
    "        dp = [[0]*full_mask for _ in range(n)]\n",
    "\n",
    "        for mask in valid_masks:\n",
    "    \n",
    "            dp[0][mask] = 1\n",
    "\n",
    "        for i in range(1,n):\n",
    "            for mask in valid_masks:\n",
    "                for prev_mask in adjacent[mask]:\n",
    "\n",
    "                    dp[i][mask] += dp[i-1][prev_mask]\n",
    "                    dp[i][mask] %= MODX\n",
    "        \n",
    "        ans = 0\n",
    "        for mask in valid_masks:\n",
    "\n",
    "            ans += dp[n-1][mask]\n",
    "        return ans%MODX\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List, Tuple\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "State = Tuple[int, ...]\n",
    "\n",
    "# 1 <= m <= 5\n",
    "# 1 <= n <= 1000\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        \"\"\"思路同2184，先状压处理每行的可能状态，再dp处理相邻行间的状态\"\"\"\n",
    "        n, m = m, n\n",
    "\n",
    "        def dfs(index: int, path: List[int]) -> None:\n",
    "            if index == n:\n",
    "                availableStates.append(tuple(path))\n",
    "                return\n",
    "\n",
    "            for next in range(3):\n",
    "                if path and path[-1] == next:\n",
    "                    continue\n",
    "                path.append(next)\n",
    "                dfs(index + 1, path)\n",
    "                path.pop()\n",
    "\n",
    "        availableStates: List[State] = []\n",
    "        dfs(0, [])\n",
    "\n",
    "        # 优化 8684 ms => 1080 ms\n",
    "        adjMap = defaultdict(set)\n",
    "        for cur in availableStates:\n",
    "            for next in availableStates:\n",
    "                if not any(cur[j] == next[j] for j in range(n)):\n",
    "                    adjMap[cur].add(next)\n",
    "                    adjMap[next].add(cur)\n",
    "\n",
    "        dp = [defaultdict(int) for _ in range(m)]\n",
    "        for state in availableStates:\n",
    "            dp[0][state] = 1\n",
    "        for i in range(1, m):\n",
    "            for preState in dp[i - 1].keys():\n",
    "                for curState in adjMap[preState]:\n",
    "                    dp[i][curState] += dp[i - 1][preState]\n",
    "                    dp[i][curState] %= MOD\n",
    "\n",
    "        res = 0\n",
    "        for state in dp[-1].keys():\n",
    "            res += dp[-1][state]\n",
    "            res %= MOD\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        m,n = n,m\n",
    "        available = []\n",
    "        def dfs(i,path):\n",
    "            if i == n:\n",
    "                available.append(tuple(path))\n",
    "                return \n",
    "            for j in range(3):\n",
    "                if path and path[-1]==j:\n",
    "                    continue\n",
    "                path.append(j)\n",
    "                dfs(i+1,path)\n",
    "                path.pop()\n",
    "        dfs(0,[])\n",
    "        # print(available)\n",
    "        adjMap = defaultdict(set)\n",
    "\n",
    "        for x in available:\n",
    "            for y in available:\n",
    "                if all(x[i]!=y[i] for i in range(n)):\n",
    "                    adjMap[x].add(y)\n",
    "                    adjMap[y].add(x)\n",
    "        # print(adjMap)\n",
    "        dp = [defaultdict(int) for _ in range(m)]\n",
    "\n",
    "        for x in available:\n",
    "            dp[0][x] = 1\n",
    "        MOD = 10**9+7\n",
    "        for i in range(1,m):\n",
    "            for prevState in dp[i-1].keys():\n",
    "                for curState in adjMap[prevState]:\n",
    "                    dp[i][curState] = (dp[i][curState] + dp[i-1][prevState]) % MOD\n",
    "        ans = 0\n",
    "        for k,v in dp[-1].items():\n",
    "            # print(k,v)\n",
    "            ans = (ans+v) % MOD\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "dp = []\n",
    "n = 1001\n",
    "for m in range(1, 6):\n",
    "\n",
    "    def dfs(i):\n",
    "        if i == m:\n",
    "            state.append(pre[:])\n",
    "            return\n",
    "        for x in [0, 1, 2]:\n",
    "            if pre and pre[-1] == x:\n",
    "                continue\n",
    "            pre.append(x)\n",
    "            dfs(i + 1)\n",
    "            pre.pop()\n",
    "        return\n",
    "\n",
    "\n",
    "    state = []\n",
    "    pre = []\n",
    "    dfs(0)\n",
    "    k = len(state)\n",
    "    dct = [[] for _ in range(k)]\n",
    "    for i in range(k):\n",
    "        for j in range(i + 1, k):\n",
    "            if all(state[i][x] != state[j][x] for x in range(m)):\n",
    "                dct[i].append(j)\n",
    "                dct[j].append(i)\n",
    "\n",
    "    cur = [[0] * k for _ in range(n)]\n",
    "    cur[1] = [1] * k\n",
    "    for x in range(2, n):\n",
    "        for j in range(k):\n",
    "            cur[x][j] = sum(cur[x - 1][w] for w in dct[j]) % mod\n",
    "    dp.append(copy.deepcopy(cur))\n",
    "\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        return sum(dp[m-1][n]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        cond = []\n",
    "\n",
    "        def bk(idx, s):\n",
    "            if idx == m:\n",
    "                cond.append(s)\n",
    "                return\n",
    "            \n",
    "            s = list(s)\n",
    "            for i in range(3):\n",
    "                if not s or i != s[-1]:\n",
    "                    bk(idx + 1, tuple(s + [i]))\n",
    "        \n",
    "        bk(0, tuple())\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, state):\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            \n",
    "            res = 0\n",
    "            for c in cond:\n",
    "                if all(state[i] != c[i] for i in range(m)):\n",
    "                    res += dfs(idx + 1, c)\n",
    "                    res %= kmod\n",
    "            return res\n",
    "        \n",
    "        ans = dfs(0, tuple([-1] * m))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        @cache\n",
    "        def dp(prev, j):\n",
    "            if j == n:\n",
    "                return 1\n",
    "\n",
    "            lines = []\n",
    "\n",
    "            def bt(path):\n",
    "                if len(path) == m:\n",
    "                    lines.append(''.join(path))\n",
    "                    return\n",
    "\n",
    "                i = len(path)\n",
    "                \n",
    "                for j in range(3):\n",
    "                    j = str(j)\n",
    "                    if (not path or path[-1] != j) and j != prev[i]:\n",
    "                        path.append(j)\n",
    "                        bt(path)\n",
    "                        path.pop()\n",
    "\n",
    "            bt([])\n",
    "\n",
    "            # print(prev, j, lines)\n",
    "\n",
    "            ret = 0\n",
    "            for line in lines:\n",
    "                ret = (ret + dp(line, j + 1)) % (int(1e9) + 7)\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp('3' * m, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "\n",
    "       def check(i: int) -> bool:\n",
    "          pre = -1\n",
    "          cnt = m\n",
    "          while cnt > 0:\n",
    "             if pre == i % 3:\n",
    "                return False\n",
    "             cnt -= 1\n",
    "             pre = i % 3\n",
    "             i //= 3\n",
    "          return True\n",
    "\n",
    "       def legal(a: int, b: int) -> bool:\n",
    "          cnt = m\n",
    "          while cnt > 0:\n",
    "             if a % 3 == b % 3:\n",
    "                return False\n",
    "             cnt -= 1\n",
    "             a //= 3\n",
    "             b //= 3\n",
    "          return True\n",
    "       \n",
    "       @cache\n",
    "       def dfs(j: int, i: int) -> int:\n",
    "          if j == n:\n",
    "             return 1\n",
    "          res = 0\n",
    "          for k in s:\n",
    "             if legal(k, i):\n",
    "                res += dfs(j + 1, k)\n",
    "                res %= MOD\n",
    "          return res\n",
    "       s = set()\n",
    "       for i in range(pow(3, m)):\n",
    "          if check(i):\n",
    "             s.add(i)\n",
    "       res = 0 \n",
    "       for i in s:\n",
    "          res += dfs(1, i)\n",
    "          res %= MOD\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "       MOD = 10 ** 9 + 7\n",
    "\n",
    "       def check(i: int) -> bool:\n",
    "          pre = -1\n",
    "          cnt = m\n",
    "          while cnt > 0:\n",
    "             if pre == i % 3:\n",
    "                return False\n",
    "             cnt -= 1\n",
    "             pre = i % 3\n",
    "             i //= 3\n",
    "          return True\n",
    "\n",
    "       def legal(a: int, b: int) -> bool:\n",
    "          cnt = m\n",
    "          while cnt > 0:\n",
    "             if a % 3 == b % 3:\n",
    "                return False\n",
    "             cnt -= 1\n",
    "             a //= 3\n",
    "             b //= 3\n",
    "          return True\n",
    "       \n",
    "       @cache\n",
    "       def dfs(j: int, i: int) -> int:\n",
    "          if j == n:\n",
    "             return 1\n",
    "          res = 0\n",
    "          for k in s:\n",
    "             if legal(k, i):\n",
    "                res += dfs(j + 1, k)\n",
    "                res %= MOD\n",
    "          return res\n",
    "       s = set()\n",
    "       for i in range(pow(3, m)):\n",
    "          if check(i):\n",
    "             s.add(i)\n",
    "       res = 0 \n",
    "       for i in s:\n",
    "          res += dfs(1, i)\n",
    "          res %= MOD\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        valid = set()\n",
    "        def factor(st):\n",
    "            factors = []\n",
    "            while st:\n",
    "                r = st % 3\n",
    "                factors.append(r)\n",
    "                st //= 3\n",
    "            if len(factors) < m:\n",
    "                factors.extend([0] * (m - len(factors)))\n",
    "            return factors\n",
    "        for st in range(pow(3, m)):\n",
    "            factors = factor(st)\n",
    "            f = True\n",
    "            for x, y in pairwise(factors):\n",
    "                if x == y: f = False; break\n",
    "            # print(f, st, factors)\n",
    "            if f: valid.add(st)\n",
    "\n",
    "        adj = defaultdict(dict)\n",
    "\n",
    "        for x in valid:\n",
    "            for y in valid:\n",
    "                if x == y: \n",
    "                    adj[x][y] = False\n",
    "                    continue\n",
    "                fx, fy = factor(x), factor(y)\n",
    "                f = True\n",
    "                for a, b in zip(fx, fy):\n",
    "                    if a == b: f = False; break\n",
    "                adj[x][y] = f\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(idx, pre):\n",
    "            if idx == n: return 1\n",
    "            res = 0\n",
    "            for cur in valid:\n",
    "                if idx == 0 or adj[pre][cur]: \n",
    "                    res += dfs(idx + 1, cur)\n",
    "                    res %= mod\n",
    "            return res\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        @cache\n",
    "        def check(arr):\n",
    "            if len(arr) != m: return False\n",
    "            for i in range(1, len(arr)):\n",
    "                if arr[i] == arr[i-1]:\n",
    "                    return False \n",
    "            return True \n",
    "        mod = 10**9+7\n",
    "\n",
    "        # 状态压缩，每一行颜色需要不同，当前一行和上一行也需要不同\n",
    "        # 三进制,243种\n",
    "\n",
    "        g = []\n",
    "        \n",
    "        for mask in range(3**m + 1):\n",
    "            arr = []\n",
    "            while mask > 0:\n",
    "                remainder = mask % 3\n",
    "                arr.append(remainder)\n",
    "                mask //= 3\n",
    "            if len(arr) < m:\n",
    "                arr += [0]*(m-len(arr))\n",
    "            arr = tuple(arr)\n",
    "            if check(arr):\n",
    "                g.append(arr)\n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            if i == n-1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for cur in g:\n",
    "                if len(cur) != len(pre): continue \n",
    "                flag = True \n",
    "                for j in range(len(cur)):\n",
    "                    if cur[j] == pre[j]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    res += dfs(i+1, cur)\n",
    "            return res % mod\n",
    "\n",
    "        res = 0\n",
    "        for mask in g:\n",
    "            res = (res + dfs(0, mask)) % mod\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        valid = set()\n",
    "        def factor(st):\n",
    "            factors = []\n",
    "            while st:\n",
    "                r = st % 3\n",
    "                factors.append(r)\n",
    "                st //= 3\n",
    "            if len(factors) < m:\n",
    "                factors.extend([0] * (m - len(factors)))\n",
    "            return factors\n",
    "        for st in range(pow(3, m)):\n",
    "            factors = factor(st)\n",
    "            f = True\n",
    "            for x, y in pairwise(factors):\n",
    "                if x == y: f = False; break\n",
    "            if f: valid.add(st)\n",
    "\n",
    "        adj = defaultdict(dict)\n",
    "\n",
    "        for x in valid:\n",
    "            for y in valid:\n",
    "                if x == y: \n",
    "                    adj[x][y] = False\n",
    "                    continue\n",
    "                fx, fy = factor(x), factor(y)\n",
    "                f = True\n",
    "                for a, b in zip(fx, fy):\n",
    "                    if a == b: f = False; break\n",
    "                adj[x][y] = f\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(idx, pre):\n",
    "            if idx == n: return 1\n",
    "            res = 0\n",
    "            for cur in valid:\n",
    "                if idx == 0 or adj[pre][cur]: \n",
    "                    res += dfs(idx + 1, cur)\n",
    "                    res %= mod\n",
    "            return res\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache,lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "\n",
    "        max_mask = 3 ** m\n",
    "        mod = int(1e9+7)\n",
    "        @cache\n",
    "        def col(i:int):\n",
    "            ret = [0] * m\n",
    "            for j in range(m):\n",
    "                ret[j] = i % 3\n",
    "                i //= 3\n",
    "            return ret\n",
    "        def check_1(c):\n",
    "            for i in range(1,len(c)):\n",
    "                if c[i] == c[i-1]:\n",
    "                    return False\n",
    "            return True\n",
    "        def check_2(d,c):\n",
    "            for i in range(len(c)):\n",
    "                if d[i] == c[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        allow = []\n",
    "        for i in range(max_mask):\n",
    "            g = col(i)\n",
    "            if check_1(g):\n",
    "                allow.append(i)\n",
    "        @cache\n",
    "        def f(mask:int,x:int):\n",
    "            if x == n:\n",
    "                return 1\n",
    "            d = col(mask)\n",
    "            ret = 0\n",
    "            if x == 0:\n",
    "                for i in allow:\n",
    "                    ret += f(i,x+1)\n",
    "            else:\n",
    "                for i in allow:\n",
    "                    c = col(i)\n",
    "                    if check_2(d,c):\n",
    "                        ret += f(i,x+1)\n",
    "            ret %= mod\n",
    "            return ret\n",
    "        return f(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        @cache\n",
    "        def check(arr):\n",
    "            if len(arr) != m: return False\n",
    "            for i in range(1, len(arr)):\n",
    "                if arr[i] == arr[i-1]:\n",
    "                    return False \n",
    "            return True \n",
    "        mod = 10**9+7\n",
    "\n",
    "        # 状态压缩，每一行颜色需要不同，当前一行和上一行也需要不同\n",
    "        # 三进制,243种\n",
    "\n",
    "        g = []\n",
    "        \n",
    "        for mask in range(3**m + 1):\n",
    "            arr = []\n",
    "            while mask > 0:\n",
    "                remainder = mask % 3\n",
    "                arr.append(remainder)\n",
    "                mask //= 3\n",
    "            if len(arr) < m:\n",
    "                arr += [0]*(m-len(arr))\n",
    "            arr = tuple(arr)\n",
    "            if check(arr):\n",
    "                g.append(arr)\n",
    "\n",
    "        # 预处理合法的转换\n",
    "        dic = defaultdict(list)\n",
    "        for mask1 in g:\n",
    "            for mask2 in g:\n",
    "                flag = True \n",
    "                for j in range(m):\n",
    "                    if mask1[j] == mask2[j]:\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    dic[mask1].append(mask2)\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            if i == n-1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for nxt in dic[pre]:\n",
    "                res += dfs(i+1, nxt)\n",
    "            return res % mod\n",
    "\n",
    "        res = 0\n",
    "        for mask in g:\n",
    "            res = (res + dfs(0, mask)) % mod\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        bag = []\n",
    "        def line(i, now):\n",
    "            if i == m:\n",
    "                bag.append(now)\n",
    "                return\n",
    "            if now%3 == 0:\n",
    "                line(i+1, now*3+1)\n",
    "                line(i+1, now*3+2)\n",
    "            elif now%3 == 1:\n",
    "                line(i+1, now*3)\n",
    "                line(i+1, now*3+2)\n",
    "            else:\n",
    "                line(i+1, now*3)\n",
    "                line(i+1, now*3+1)\n",
    "        for i in range(3):\n",
    "            line(1, i)\n",
    "        @cache\n",
    "        def fun(lastLine, now):\n",
    "            if now == n:\n",
    "                return 1\n",
    "            sumnum = 0\n",
    "            for e in bag:\n",
    "                temp = lastLine\n",
    "                te = e\n",
    "                flag = True\n",
    "                for i in range(m):\n",
    "                    if te % 3 == temp % 3:\n",
    "                        flag = False\n",
    "                        break\n",
    "                    te //= 3\n",
    "                    temp //= 3\n",
    "                if flag:\n",
    "                    sumnum += fun(e, now+1)\n",
    "            return sumnum\n",
    "        res = 0\n",
    "        for what in bag:\n",
    "            res += fun(what, 1)\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def colorTheGrid(self, m: int, n: int) -> int:\n",
    "        \"\"\"\n",
    "        color 1 2 3\n",
    "        :param m:\n",
    "        :param n:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(cur_idx, prev_line, prev_tag=-1):\n",
    "            if cur_idx == m:\n",
    "                return [[]]\n",
    "            if len(prev_line) == 0:\n",
    "                ans = []\n",
    "                for i in range(1, 4):\n",
    "                    if i != prev_tag:\n",
    "                        ans1 = get_cnt(cur_idx + 1, prev_line, i)\n",
    "                        for x in ans1:\n",
    "                            ans.append([i] + x)\n",
    "                return ans\n",
    "            else:\n",
    "                ans = []\n",
    "                for i in range(1, 4):\n",
    "                    if i != prev_tag and prev_line[cur_idx] != i:\n",
    "                        ans1 = get_cnt(cur_idx + 1, prev_line, i)\n",
    "                        for x in ans1:\n",
    "                            ans.append([i] + x)\n",
    "                return ans\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def get_cnt2(idx, prev_line = None):\n",
    "            if idx == n:\n",
    "                return 1\n",
    "            if prev_line is None:\n",
    "                retlist = get_cnt(0, tuple([]))\n",
    "                ans = 0\n",
    "                for i in retlist:\n",
    "                    ans1 = get_cnt2(idx + 1, tuple(i))\n",
    "                    ans += ans1\n",
    "                return ans\n",
    "            else:\n",
    "                retlist = get_cnt(0, prev_line)\n",
    "                ans = 0\n",
    "                for i in retlist:\n",
    "                    ans1 = get_cnt2(idx + 1, tuple(i))\n",
    "                    ans += ans1\n",
    "                return ans\n",
    "        return get_cnt2(0) % (10 ** 9 + 7)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
